5.1.1 Algoritmo de enrutamiento de estado de enlaces (LS)
En un algoritmo de estado de enlaces, la topología de la red y el coste de todos los enlaces son conocidos; es decir, están disponibles como entradas para el algoritmo LS. En la práctica, esto se consigue haciendo que cada nodo difunda paquetes del estado de los enlaces a todos los demás nodos de la red, con cada paquete de estado de enlace conteniendo las identidades y los costes de sus enlaces conectados.
El resultado de difundir la información de los nodos es que todos los nodos tienen una visión completa e idéntica de la red. Cada nodo puede entonces ejecutar el algoritmo LS y calcular el mismo conjunto de rutas de coste mínimo que cualquier otro nodo.
El algoritmo de Dijkstra calcula la ruta de coste mínimo desde un nodo (el origen, al que denominaremos u) hasta todos los demás nodos de la red.
# inicialización:
N’ = {u}
D : distancias a cada nodo
P : predecesor en el camino de costo mínimo
for todo nodo v
if v es un vecino de u:
D(v) = c(u,v);
P(v) = u
else:
D(v) = ∞;
do
encontrar w no perteneciente a N’ tal que D(w) sea un mínimo;
agregar w a N’;
actualizar D(v) para cada vecino v de w, que no pertenezca a N’:
D(v) = min( D(v), D(w) + c(w,v) );
# el nuevo coste a v es o bien el antiguo
# coste a v o el coste de la ruta de coste
# mínimo a w más el coste desde w a v
if se modificó D(v):
P(v) = w
until N’ = N
Cuando el algoritmo LS termina, tenemos para cada nodo su predecesor a lo largo de la ruta de coste mínimo desde el nodo de origen. Para cada predecesor, también tenemos su predecesor, y así de este modo podemos construir la ruta completa desde el origen a todos los destinos.
El número total de nodos a través de los que tenemos que buscar teniendo en cuenta todas las iteraciones es igual a
Una implementación más eficiente tiene
